package DataStructure.geometry;


import java.util.*;

//凸包问题
public class ConvexHull {

    //Jarvis算法
    //如果最外层的点都按某个方向面朝下一个外点,形成逆时针的圆,
    //那么对于某个外点指向下一个点的向量,所有点都在线上或者左边
    public int[][] Jarvis(int[][] points){
        int n=points.length;
        if(n<=3)
            return points;
        List<int[]> list=new ArrayList<>();//存储外点
        boolean[] mark=new boolean[n];//标记已经添加的点
        int begin=0;//以最左边的点作为开始,一定为外点
        for (int i = 0; i < n; i++) {
            if(points[i][0]<points[begin][0])
                begin=i;
        }
        int p=begin;//每次寻找的基点
        while (true){
            int q=(p+1)%n;//从p下一个点开始,记录p最右边的点
            //寻找相对pq最右边的点r
            for (int r = 0; r <n ; r++) {
                //只要叉乘<0,说明r在pq右边
                if(cross(points[p],points[q],points[r])<0)
                    q=r;
            }
           //寻找pq线上的点
            for (int i = 0; i < n; i++) {
                if(mark[i]||i==p||i==q)
                    continue;
                if(cross(points[p],points[q],points[i])==0){
                    list.add(points[i]);
                    mark[i]=true;
                }
            }
            //q可能已经被某条线上其他点标记
            if(!mark[q]){
                list.add(points[q]);
                mark[q]=true;
            }
            if(q==begin)//回到起点
                break;
            p=q;
        }
        return list.toArray(new int[][]{});
    }
    //叉乘pq*qr
    public int cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

    //Andrew算法
    //从左到右,从下到上遍历外点入栈,从而形成逆时针的圆
    //对于下一个点,如果栈顶向量(peek-1,peek)*(peek,i)<0,说明i点在(peek-1,peek)右边,那么peek出栈i入栈
    //第一次找出下半圆,第二次找出上半圆
    public int[][] Andrew(int[][] points){
        int n=points.length;
        if(n<=3)
            return points;
        List<Integer> list=new ArrayList<>();//存储外点
        boolean[] mark=new boolean[n];//标记已经添加的点
        //先x后y,从小到大排序
        Arrays.sort(points, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        list.add(0);//左下起点,起点不标记,求上半部分时需要回到起点
        //下半部分
        for (int i = 1; i <n ; i++) {
            //只要叉乘<0则出栈,直到i处于栈顶向量左边
            while(list.size()>1&&cross(points[list.get(list.size()-2)],points[list.get(list.size()-1)],points[i] )<0){
                mark[list.remove(list.size()-1)]=false;
            }
            list.add(i);
            mark[i]=true;
        }
        int m=list.size();
        //上半部分
        for (int i = n-1; i >=0 ; i--) {
            if(!mark[i]){
                while(list.size()>m&&cross(points[list.get(list.size()-2)],points[list.get(list.size()-1)],points[i])<0){
                    mark[list.remove(list.size()-1)]=false;
                }
                list.add(i);
                mark[i]=true;
            }
        }
        list.remove(list.size()-1);//起点添加了两次
        int len=list.size();
        int[][] ans=new int[len][2];
        for (int i = 0; i <len ; i++) {
            ans[i][0]=points[list.get(i)][0];
            ans[i][1]=points[list.get(i)][1];
        }
        return ans;

    }




}
